package com.ddd.demo.lee.堆;

public class MinHeap {
    private int[] heap;
    private int size;

    public MinHeap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }

    // 上移操作，用于调整堆
    private void siftUp(int index) {
        while (index > 0 && heap[index] < heap[getParent(index)]) {
            swap(index, getParent(index));
            index = getParent(index);
        }
    }

    // 交换两个元素位置
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    // 获取父节点索引
    private int getParent(int index) {
        return (index - 1) / 2;
    }

    // 插入元素到堆中
    public void insert(int value) {
        if (size == heap.length) {
            throw new RuntimeException("堆已满");
        }
        heap[size++] = value;
        siftUp(size - 1);
    }

    // 获取堆顶元素（最小值）
    public int peek() {
        if (size == 0) {
            throw new RuntimeException("堆为空");
        }
        return heap[0];
    }

    // 删除堆顶元素
    public int remove() {
        if (size == 0) {
            throw new RuntimeException("堆为空");
        }
        int min = heap[0];
        heap[0] = heap[size - 1];
        size--;
        siftDown(0);
        return min;
    }

    // 下移操作，用于调整堆
    private void siftDown(int index) {
        int minIndex = index;
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;

        if (leftChild < size && heap[leftChild] < heap[minIndex]) {
            minIndex = leftChild;
        }

        if (rightChild < size && heap[rightChild] < heap[minIndex]) {
            minIndex = rightChild;
        }

        if (minIndex!= index) {
            swap(index, minIndex);
            siftDown(minIndex);
        }
    }

    public static void main(String[] args) {
        MinHeap minHeap = new MinHeap(10);
        minHeap.insert(5);
        minHeap.insert(3);
        minHeap.insert(7);
        minHeap.insert(1);

        System.out.println(minHeap.peek());
        System.out.println(minHeap.remove());
    }
}